package com.dataStructures.stack;

import java.util.HashMap;
import java.util.Map;

/**
 * 栈实现计算器 - 中缀表达式
 */
public class Calculator {
	public static void main(String[] args) {
		String expression = "7*2-2*3+1";
		// 数栈
		ArrayStack1 numStack = new ArrayStack1(20);
		// 符号栈
		ArrayStack1 operStack = new ArrayStack1(20);
		int num1, num2, oper, res, index = 0;
		char ch = ' ';
		// 用于拼接多位数
		String keepNum = "";

		while (true) {
			ch = expression.charAt(index);
			if (operStack.isOper(ch)) {
				if (!operStack.isEmpty()) {
					if (operStack.getPriority(ch) <= operStack.getPriority(operStack.peek())) {
						num1 = numStack.pop();
						num2 = numStack.pop();
						oper = operStack.pop();
						res = numStack.cal(num1, num2, oper);
						numStack.push(res);
						operStack.push(ch);
					} else {
						operStack.push(ch);
					}
				} else {
					operStack.push(ch);
				}
			} else {
				keepNum += ch;
				if (index == expression.length() - 1) {
					numStack.push(Integer.parseInt(keepNum));
				} else if (operStack.isOper(expression.charAt(index + 1))) {
					numStack.push(Integer.parseInt(keepNum));
					keepNum = "";
				}
			}
			if (++index >= expression.length()) {
				break;
			}
		}
		// 表达式扫描完，就顺序从数栈和符号栈中取出内容运行
		while (true) {
			if (operStack.isEmpty()) {
				break;
			}
			num1 = numStack.pop();
			num2 = numStack.pop();
			oper = operStack.pop();
			res = numStack.cal(num1, num2, oper);
			numStack.push(res);
		}
		System.out.printf("express: %s = %d", expression, numStack.pop());
	}
}

class ArrayStack1 {
	private final int maxSize;
	private final int[] stack;
	private int top = -1;

	private static final Map<Character, Integer> priorityMap = new HashMap();

	static {
		priorityMap.put('+', 0);
		priorityMap.put('-', 0);
		priorityMap.put('*', 1);
		priorityMap.put('/', 1);
	}

	public ArrayStack1(int maxSize) {
		this.maxSize = maxSize;
		stack = new int[maxSize];
	}

	public boolean isFull() {
		return top == maxSize - 1;
	}

	public boolean isEmpty() {
		return top == -1;
	}

	public void push(int val) {
		if (isFull()) {
			System.out.println("stack full");
			return;
		}
		stack[++top] = val;
	}

	public int pop() {
		if (isEmpty()) {
			throw new RuntimeException("stack empty");
		}
		return stack[top--];
	}

	public void show() {
		if (isEmpty()) {
			System.out.println("stack empty");
			return;
		}
		for (int i = top; i >= 0; i--) {
			System.out.printf("stack[%d]=%d\n", i, stack[i]);
		}
	}

	/**
	 * 返回栈顶的值
	 */
	public int peek() {
		return stack[top];
	}

	/**
	 * 返回运算符的优先级，数字越大，优先级越高
	 */
	public int getPriority(int oper) {
		Integer priority = priorityMap.get((char) oper);
		if (priority != null) {
			return priority;
		}
		return -1;
	}

	/**
	 * 判断是不是一个运算符
	 */
	public boolean isOper(char oper) {
		return priorityMap.containsKey(oper);
	}

	/**
	 * 计算
	 */
	public int cal(int num1, int num2, int oper) {
		int res = 0;
		switch (oper) {
			case '+':
				res = num1 + num2;
				break;
			case '-':
				// 注意顺序
				res = num2 - num1;
				break;
			case '*':
				res = num1 * num2;
				break;
			case '/':
				res = num2 / num1;
				break;
			default:
				break;
		}
		return res;
	}
}

